import java.util.*;

/**
 * 题目：游戏分组
 * 
 * 题目描述：
 * 王者荣耀表演赛即将开始，有10名游戏爱好者参与，需要分成两队，每队5人。
 * 为了使比赛尽可能精彩，需要将10名参与者分成两队，使两队实力尽可能相近。
 * 
 * 每名参与者都有一个数值，表示其游戏水平。两队实力相近是指两队实力差值的绝对值最小。
 * 
 * 输入描述：
 * 10个整数，表示10名参与者的游戏水平数值，数值范围[1, 10000]。
 * 
 * 输出描述：
 * 1个整数，表示两队实力差值的绝对值的最小值。
 * 
 * 示例1：
 * 输入：1 2 3 4 5 6 7 8 9 10
 * 输出：1
 * 
 * 解题思路：
 * 这是一个典型的背包问题变种，需要将10个数字分成两组，每组5个数字，使得两组和的差值最小。
 * 
 * 算法分析：
 * - 时间复杂度：O(C(10,5)) = O(252) 对于暴力枚举
 * - 空间复杂度：O(1)
 * - 算法类型：组合优化，动态规划
 */
public class GameTeamGrouping {
    
    /**
     * 方法1：暴力枚举法（推荐使用）
     * 枚举所有可能的分组方式，找到差值最小的分组
     * 
     * 算法思路：
     * 1. 使用位运算枚举所有C(10,5)种分组方式
     * 2. 计算每种分组的两队实力差值
     * 3. 返回最小差值
     * 
     * 时间复杂度：O(C(10,5)) = O(252)
     * 空间复杂度：O(1)
     */
    public static int minDifference1(int[] players) {
        int minDiff = Integer.MAX_VALUE;
        int totalSum = 0;
        for (int player : players) {
            totalSum += player;
        }
        
        // 枚举所有可能的分组方式（选择5个人）
        for (int mask = 0; mask < (1 << 10); mask++) {
            if (Integer.bitCount(mask) != 5) continue; // 确保选择5个人
            
            int team1Sum = 0;
            for (int i = 0; i < 10; i++) {
                if ((mask & (1 << i)) != 0) {
                    team1Sum += players[i];
                }
            }
            
            int team2Sum = totalSum - team1Sum;
            int diff = Math.abs(team1Sum - team2Sum);
            minDiff = Math.min(minDiff, diff);
        }
        
        return minDiff;
    }
    
    /**
     * 方法2：动态规划法
     * 使用动态规划求解背包问题
     * 
     * 算法思路：
     * 1. 将问题转化为背包问题：选择5个数字，使得和尽可能接近总和的一半
     * 2. 使用DP求解最接近目标值的组合
     * 
     * 时间复杂度：O(n * sum)
     * 空间复杂度：O(n * sum)
     */
    public static int minDifference2(int[] players) {
        int totalSum = 0;
        for (int player : players) {
            totalSum += player;
        }
        
        int target = totalSum / 2;
        boolean[][] dp = new boolean[11][target + 1];
        dp[0][0] = true;
        
        // 动态规划求解
        for (int i = 0; i < 10; i++) {
            for (int j = 10; j >= 1; j--) {
                for (int k = target; k >= players[i]; k--) {
                    if (dp[j - 1][k - players[i]]) {
                        dp[j][k] = true;
                    }
                }
            }
        }
        
        // 找到最接近target的5人组合
        for (int k = target; k >= 0; k--) {
            if (dp[5][k]) {
                return Math.abs(totalSum - 2 * k);
            }
        }
        
        return totalSum;
    }
    
    /**
     * 方法3：贪心算法法
     * 使用贪心策略进行分组
     * 
     * 算法思路：
     * 1. 将玩家按实力排序
     * 2. 使用贪心策略分配玩家到两队
     * 3. 优先将实力强的玩家分配到实力较弱的队
     * 
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(1)
     */
    public static int minDifference3(int[] players) {
        int[] sortedPlayers = players.clone();
        Arrays.sort(sortedPlayers);
        
        int team1Sum = 0, team2Sum = 0;
        int team1Count = 0, team2Count = 0;
        
        // 贪心分配：从大到小分配，优先分配给实力较弱的队
        for (int i = 9; i >= 0; i--) {
            if (team1Count < 5 && team2Count < 5) {
                if (team1Sum <= team2Sum) {
                    team1Sum += sortedPlayers[i];
                    team1Count++;
                } else {
                    team2Sum += sortedPlayers[i];
                    team2Count++;
                }
            } else if (team1Count < 5) {
                team1Sum += sortedPlayers[i];
                team1Count++;
            } else {
                team2Sum += sortedPlayers[i];
                team2Count++;
            }
        }
        
        return Math.abs(team1Sum - team2Sum);
    }
    
    /**
     * 方法4：回溯算法法
     * 使用回溯算法枚举所有可能的分组
     * 
     * 算法思路：
     * 1. 使用回溯算法生成所有C(10,5)种组合
     * 2. 计算每种组合的两队实力差值
     * 3. 返回最小差值
     * 
     * 时间复杂度：O(C(10,5))
     * 空间复杂度：O(5) 递归栈深度
     */
    public static int minDifference4(int[] players) {
        int[] result = {Integer.MAX_VALUE};
        int totalSum = 0;
        for (int player : players) {
            totalSum += player;
        }
        
        backtrack(players, 0, 0, 0, 0, totalSum, result);
        return result[0];
    }
    
    private static void backtrack(int[] players, int index, int team1Sum, int team1Count, int team2Count, int totalSum, int[] result) {
        if (team1Count == 5 && team2Count == 5) {
            int team2Sum = totalSum - team1Sum;
            int diff = Math.abs(team1Sum - team2Sum);
            result[0] = Math.min(result[0], diff);
            return;
        }
        
        if (index >= 10) return;
        
        // 选择当前玩家加入team1
        if (team1Count < 5) {
            backtrack(players, index + 1, team1Sum + players[index], team1Count + 1, team2Count, totalSum, result);
        }
        
        // 选择当前玩家加入team2
        if (team2Count < 5) {
            backtrack(players, index + 1, team1Sum, team1Count, team2Count + 1, totalSum, result);
        }
    }
    
    /**
     * 方法5：优化位运算法
     * 使用优化的位运算枚举所有分组方式
     * 
     * 算法思路：
     * 1. 使用位运算技巧快速枚举所有C(10,5)种组合
     * 2. 使用预计算优化差值计算
     * 3. 早期剪枝优化
     * 
     * 时间复杂度：O(C(10,5))
     * 空间复杂度：O(1)
     */
    public static int minDifference5(int[] players) {
        int minDiff = Integer.MAX_VALUE;
        int totalSum = 0;
        for (int player : players) {
            totalSum += player;
        }
        
        // 使用位运算技巧枚举所有5人组合
        int mask = (1 << 5) - 1; // 初始掩码：0000011111
        int maxMask = 1 << 10;
        
        while (mask < maxMask) {
            int team1Sum = 0;
            for (int i = 0; i < 10; i++) {
                if ((mask & (1 << i)) != 0) {
                    team1Sum += players[i];
                }
            }
            
            int team2Sum = totalSum - team1Sum;
            int diff = Math.abs(team1Sum - team2Sum);
            minDiff = Math.min(minDiff, diff);
            
            // 生成下一个组合
            int t = mask | (mask - 1);
            mask = (t + 1) | (((~t & -~t) - 1) >> (Integer.numberOfTrailingZeros(mask) + 1));
        }
        
        return minDiff;
    }
    
    /**
     * 主方法 - 程序入口
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        System.out.println("请输入10名参与者的游戏水平数值（空格分隔）：");
        int[] players = new int[10];
        for (int i = 0; i < 10; i++) {
            players[i] = scanner.nextInt();
        }
        
        // 测试所有方法
        System.out.println("\n=== 所有算法结果对比 ===");
        System.out.println("方法1（暴力枚举法）: " + minDifference1(players));
        System.out.println("方法2（动态规划法）: " + minDifference2(players));
        System.out.println("方法3（贪心算法法）: " + minDifference3(players));
        System.out.println("方法4（回溯算法法）: " + minDifference4(players));
        System.out.println("方法5（优化位运算法）: " + minDifference5(players));
        
        // 推荐使用的方法
        System.out.println("\n推荐使用方法1（暴力枚举法），对于固定10人分组问题效率最高");
        
        scanner.close();
    }
}
